package main.leetcode.clockin.May;

import main.datastruc.TreeNode;

/**
 * 236.二叉树的最近公共祖先
 *
 * <p>给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * <p>百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * <p>例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
 *
 * <p>说明: 所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉树中。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day10 {
    //    private TreeNode res;

    public static void main(String[] args) {
        TreeNode root = TreeNode.creCmpBTree(new int[] {3, 5, 1, 6, 2, 0, 8, 10, 11, 7, 4});
        TreeNode p = TreeNode.creCmpBTree(new int[] {0, 8, 10, 11, 7, 4});
        TreeNode q = TreeNode.creCmpBTree(new int[] {8, 10, 11, 7, 4});
        TreeNode res = new day10().lowestCommonAncestor(root, p, q);
        System.out.println(res);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode left = null;
        if (root.left != null) {
            left = lowestCommonAncestor(root.left, p, q);
        }
        TreeNode right = null;
        if (root.right != null) {
            right = lowestCommonAncestor(root.right, p, q);
        }

        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
    //    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //
    //        if (root.left != null) {
    //            res = lowestCommonAncestor(root.left, p, q);
    //        }
    //        if (res == null && root.right != null) {
    //            lowestCommonAncestor(root.right, p, q);
    //        }
    //        if (res == null && has(root, p) && has(root, q)) {
    //            res = root;
    //        }
    //        return res;
    //    }
    //
    //    private boolean has(TreeNode root, TreeNode q) {
    //        if (root == null) {
    //            return false;
    //        }
    //        return root.val == q.val || has(root.left, q) || has(root.right, q);
    //    }
}
